local c_algorithm  = require "algorithm.c"

local _random = math.random
local algorithm = {}

algorithm.hash = c_algorithm.hash
algorithm.murmur_hash = c_algorithm.murmur_hash

-- 用于判断table是否为空
-- t为空或nil，返回true，否则返回false
local function is_tbl_empty(t)
    return not t or not next(t)
end

-- list table 浅拷贝
local function tbl_copy(t, ret)
    if not t then
        return
    end
    ret = ret or {}
    for _, v in ipairs(t) do
        table.insert(ret, v)
    end
    return ret
end

-- 随机取list table中的一个元素
function algorithm.tbl_random_one(tbl, random)
    random = random or _random
    if is_tbl_empty(tbl) then
        return
    end
    return tbl[random(#tbl)]
end

-- 随机取list table中n个不重复元素(所有元素等权重)
-- @params tbl list table
-- @params num 待取元素个数
-- @params ret(out) 取到的元素插入此table
-- @params random 自定义随机函数
-- @return ret
function algorithm.tbl_random(tbl, num, ret, random)
    if is_tbl_empty(tbl) or num <= 0 then
        return
    end
    ret = ret or {}
    random = random or _random

    if num == 1 then
        table.insert(ret, algorithm.tbl_random_one(tbl, random))
        return ret
    elseif num >= #tbl then
        tbl_copy(tbl, ret)
        return ret
    end

    -- 1 < num < #tbl
    local remain = #tbl
    while num > 0 do
        while remain > 0 do
            local ran = random(remain)
            if ran <= num then
                table.insert(ret, tbl[remain])
                remain = remain - 1
                break
            end
            remain = remain - 1
        end
        num = num - 1
    end

    return ret
end

-- 计算总权重
local function calc_total_weight(tbl, weight_key)
    weight_key = weight_key or "weight"
    local total_weight = 0
    for _, v in ipairs(tbl) do
        total_weight = total_weight + v[weight_key]
    end
    return total_weight
end

-- 随机取list table中1个元素(所有元素权重不一定相等)
-- 参数含义同algorithm.group_random()
function algorithm.group_random_one(group, params)
    if is_tbl_empty(group) then
        return
    end
    params = params or {}
    local random = params.random or _random

    local weight_key = params.weight_key or "weight"
    local total_weight = params.total_weight or calc_total_weight(group, weight_key)
    local ran = random(total_weight)
    for _, v in ipairs(group) do
        if ran > v[weight_key] then
            ran = ran - v[weight_key]
        else
            return v
        end
    end
end

-- 随机取list table中n个不重复元素(所有元素权重不一定相等)
-- @params group list table，每个元素也是table，有key指明了本元素的权重
-- @params num 取元素的个数
-- @params params 额外参数表
--    目前支持的额外参数
--    params = {
--        weight_key   = k  -- 字符串或数字，用于指明元素权重在元素table中的key的名称
--        total_weight = 0, -- 所有元素总权重
--        random       = function -- 自定义随机函数
--    }
-- @params ret(out) 取到的元素插入此table
-- @return ret
function algorithm.group_random(group, num, params, ret)
    if is_tbl_empty(group) or num <= 0 then
        return
    end
    params = params or {}
    ret = ret or {}
    local random = params.random or _random

    if num == 1 then
        table.insert(ret, algorithm.group_random_one(group, params))
        return ret
    elseif num >= #group then
        tbl_copy(group, ret)
        return ret
    end

    -- 1 < num < #tbl
    -- 浅拷贝group
    group = tbl_copy(group)
    local length = #group
    local weight_key = params.weight_key or "weight"
    local total_weight = params.total_weight or calc_total_weight(group, weight_key)

    for i = 1, num do
        local ran = random(total_weight)
        for j = i, length do
            if ran > group[j][weight_key] then
                ran = ran - group[j][weight_key]
            else
                table.insert(ret, group[j])
                total_weight = total_weight - group[j][weight_key]
                group[i], group[j] = group[j], group[i]
                break
            end
        end
    end
    return ret
end

-- 重复执行algorithm.group_random()函数n次
-- 参数含义同algorithm.group_random()
-- 参数params额外新增count字段，用于指明重复执行次数，不传默认1
function algorithm.group_random_repeat(group, num, params, ret)
    params = params or {}
    ret = ret or {}

    local count = params.count or 1
    for _ = 1, count do
        algorithm.group_random(group, num, params, ret)
    end
    return ret
end

return algorithm
